package com.atguigui.leetcode1;

import java.util.HashMap;
import java.util.Map;

/**
 * 2287.重排字符形成目标字符串
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/1/13 8:44
 */
public class P2287RearrangeCharactersToMakeTargetString {
    public static void main(String[] args) {
        Solution solution = new P2287RearrangeCharactersToMakeTargetString().new Solution();
        // TO TEST
        solution.rearrangeCharacters("ilovecodingonleetcode", "");
    }

    class Solution {
        public int rearrangeCharacters(String s, String target) {
            //记录 sss 和 target\textit{target}target 的每个字符的出现次数
            Map<Character, Integer> sCounts = new HashMap<Character, Integer>();
            Map<Character, Integer> targetCounts = new HashMap<Character, Integer>();
            int n = s.length(), m = target.length();
            //target
            for (int i = 0; i < m; i++) {
                char c = target.charAt(i);
                targetCounts.put(c, targetCounts.getOrDefault(c, 0) + 1);
            }
            //s
            for (int i = 0; i < n; i++) {
                char c = s.charAt(i);
                if (targetCounts.containsKey(c)) {
                    sCounts.put(c, sCounts.getOrDefault(c, 0) + 1);
                }
            }
            int ans = Integer.MAX_VALUE;
            for (Map.Entry<Character, Integer> entry : targetCounts.entrySet()) {
                char c = entry.getKey();
                int count = entry.getValue();
                int totalCount = sCounts.containsKey(c) ? sCounts.get(c) : 0;
                //s中出现的次数 / target中出现的次数
                ans = Math.min(ans, totalCount / count);
                if (ans == 0) {
                    return 0;
                }
            }
            return ans;
        }
    }
}
